package com.leetcode.根据数据结构分类.并查集;

/**
 * @author: xiaomi
 * @date: 2021/1/31
 * @description: 839. 相似字符串组
 * https://leetcode-cn.com/problems/similar-string-groups/
 */
public class C_839_相似字符串组 {

    public static void main(String[] args) {
        String[] str = new String[]{"tars", "rats", "arts", "star"};
        str = new String[]{"omv", "ovm"};
        C_839_相似字符串组 action = new C_839_相似字符串组();
        int res = action.numSimilarGroups(str);
        System.out.println("res = " + res);
    }

    /**
     * 难点：
     * 1.如何快速判断相似性；
     * --
     * 跟官方题解基本一致
     * @param strs
     * @return
     */
    public int numSimilarGroups(String[] strs) {
        int len = strs.length;
        //字符串的长度
        int strLen = strs[0].length();
        InnerUnionFind unionFind = new InnerUnionFind(len);
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (!unionFind.isSame(i, j)) {
                    if (isSimilar(strs[i], strs[j], strLen)) {
                        unionFind.union(i, j);
                    }
                }
            }
        }
        return unionFind.count;
    }


    private boolean isSimilar(String str1, String str2, int strLen) {
        int[] array = new int[3];
        int count = 0;
        for (int i = 0; i < strLen; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                array[count++] = i;
            }
            if (count > 2) {
                return false;
            }
        }
//        if (count == 0 || str1.charAt(array[0]) == str2.charAt(array[1])) {
//            return true;
//        }
        return true;
    }

    class InnerUnionFind {
        int[] parents;
        int[] ranks;
        /**
         * 连通个数
         */
        int count = 0;

        public InnerUnionFind(int capacity) {
            parents = new int[capacity];
            ranks = new int[capacity];
            for (int i = 0; i < capacity; i++) {
                parents[i] = i;
                ranks[i] = 1;
            }
            count = capacity;
        }

        int find(int index) {
            if (parents[index] != index) {
                parents[index] = find(parents[index]);
            }
            return parents[index];
        }

        void union(int index1, int index2) {
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 == p2) {
                return;
            }
            count--;
            if (ranks[p1] == ranks[p2]) {
                parents[p1] = parents[p2];
                ranks[p2]++;
            } else if (ranks[p1] < ranks[p2]) {
                parents[p1] = parents[p2];
            } else {
                parents[p2] = parents[p1];
            }
        }

        boolean isSame(int index1, int index2) {
            return find(index1) == find(index2);
        }
    }
}
